/**
 * 
 * @author max
 * Generic MaxHeap code, made by modifying book code.
 */
public class HeapGeneric<T extends Comparable<? super T>> {
	private int size;
	private T[] heap;

	/**
	 * Constructor. Size 4 is arbitrary.
	 */
	public HeapGeneric(){
		this(4);
	}

	/**
	 * Constructor for the generic heap. The heap is just an array of size size+1,
	 * because 0 isn't used in the ranked array repressentation.
	 * @param capacity initial capacity of the heap.
	 */
	@SuppressWarnings("unchecked")
	public HeapGeneric(int capacity){
		size = 0;

		heap = (T[]) new Comparable[capacity + 1];
	}	

	/**
	 * Insert method for the heap. The first half checks if the heap isn't full,
	 * and increases the capacity if it is. The second half percolates values up.
	 * @param o T to insert.
	 * @return boolean success.
	 */
	public boolean insert(T o ){

		if(isFull()){
			T[] temp = heap;
			heap = (T[]) new Comparable[size*2 + 1];
			for(int i = 0; i < temp.length; i++)
				heap[i] = temp[i];
		}

		int hole = ++size; 
		for ( ; hole > 1 && o.compareTo(heap[hole/2])>0; hole/=2) //percolate up
			heap[hole] = heap[hole/2];
		heap[hole] = o;
		return true;
	}

	/**
	 * toString method, returns the heap's array representation.
	 * @return String of the array.
	 */
	public String toString(){
		String s = "[ ";
		for(T o: heap){
			if(o!=null)
				s += o + ", " ;
		}
		return s.substring(0,s.length()-2) + " ]";
	}

	/**
	 * Returns the number of elements in the array. 
	 * @return int of the number of elements in the array.
	 */
	public int getSize(){
		return size;
	}

	/**
	 * Returns the value in position 1 of the array, which will
	 * always be the max value.
	 * @return T at index 1.
	 */
	public T findMax( )
	{
		if( isEmpty( ) )
			return null;
		return heap[ 1 ];
	}

	/**
	 * Deletes the value at index 1 and then restores heap order.
	 * @return T that was deleted.
	 */
	public T deleteMax( )
	{
		if( isEmpty( ) )
			return null;
		if(size == 1){ 
			T maxItem = findMax( );
			makeEmpty();
			return maxItem;
		}
		T maxItem = findMax( );
		heap[ 1 ] = heap[ size-- ];
		percolateDown( 1 );

		return maxItem;
	}
	
	/**
	 * Checks if the heap is full or not.
	 * @return true if full.
	 */
	public boolean isFull( )
	{
		return size == heap.length - 1;
	}

	/**
	 * Checks if the heap is empty or not
	 * strictly based on size.
	 * @return true if empty.
	 */
	public boolean isEmpty( )
	{
		return size == 0;
	}

	/**
	 * Clears out the heap and resets the size, needed
	 * for reinserting values after a defrag.
	 */
	public void makeEmpty( )
	{
		size = 0;
		heap = (T[])new Comparable[5];
	}

	/**
	 * percolateDown method for use in deletions to restore heap order
	 * @param hole The location of the "hole," where we check if its children is greater than itself.
	 */
	private void percolateDown( int hole )
	{
		int child;
		T tmp = heap[ hole ];

		for( ; hole * 2 <= size; hole = child ){
			child = hole * 2;
			if( child != size &&
					heap[ child + 1 ].compareTo( heap[ child ] ) > 0 )
				child++;
			if( heap[ child ].compareTo( tmp ) > 0 )
				heap[ hole ] = heap[ child ];
			else
				break;
		}
		heap[ hole ] = tmp;
	}

}
